package Top101K;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author quan
 * @Description 数组中出现次数超过一半的数字
 * @Date 2023/11/20 11:52
 */
public class BM51_MoreThanHalfNum_Solution {
    public static void main(String[] args) {
        int[] arr = {3,3,3,3,3,2,2,2,2};
        int res = MoreThanHalfNum_Solution(arr);
        System.out.println(res);

    }
    public static int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        //1-创建一个Hash表，key是数组元素，value是出现次数
        //2-判断hash表中的value是不是大于mid值；
        //3-是的话，直接从hash表中获取该值
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if(!map.containsKey(numbers[i])){
                map.put(numbers[i],1);
            }else{
                map.put(numbers[i],map.get(numbers[i])+1);
            }
        }
        int res = 0;
        for(Map.Entry<Integer, Integer> m : map.entrySet()){
            if(m.getValue() > numbers.length/2){
                res =  m.getKey();
                break;
            }
        }
        return res;
    }
}
